The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
In computer networks such as the Internet, packets of data are sent from a source to a destination via a network of links (communication paths such as telephone or optical lines) and nodes (usually routers directing the packet along one or more of a plurality of links connected to it) according to one of various routing protocols.
One class of routing protocol is the link state protocol. The link state protocol relies on a routing algorithm resident at each node. Each node on the network advertises, throughout the network, links to neighboring nodes and provides a cost associated with each link which can be based on any appropriate metric such as link bandwidth or delay and is typically expressed as an integer value. A link may have an asymmetric cost, that is, the cost in the direction AB along a link may be different from the cost in a direction BA. Based on the advertised information in the form of a link state packet (LSP) each node constructs a link state database (LSDB) which is a map of the entire network topology and from that constructs generally a single optimum route to each available node based on an appropriate algorithm such as, for example, a shortest path first (SPF) algorithm. As a result a “spanning tree” is constructed, rooted at the node and showing an optimum path including intermediate nodes to each available destination node. Because each node has a common LSDB (other than when advertised changes are propagating around the network) any node is able to compute the spanning tree rooted at any other node. The results of the SPF are stored in a routing information base (RIB) and based on these results the forwarding information base (FIB) or forwarding table is updated to control forwarding of packets appropriately.
As a result when a packet for a destination node arrives at a node (which we term here the “first node”), the first node identifies the optimum route to that destination and forwards the packet to the next node along that route. The next node repeats this step and so forth. In some circumstances it is desirable to have more control over the route that a packet takes in which case “tunneling” can be used. According to this scheme if a node A receives a packet destined for node Z and for some reason it is desired that the packet should travel via node Y, under normal circumstances node A would have no control over this (unless Y was an adjacent node), as the route is dependent on the forwarding table generated as a result of the SPF at node A and any intermediate nodes as well. However node A can “tunnel” the packet to node Y by encapsulating the received packet within a packet having destination node Y and sending it to node Y which acts as the tunnel end point. When the packet is received at node Y it is decapsulated and Y then forwards the original packet to node Z according to its standard forwarding table. Yet further control is available using directed forwarding in which the encapsulated packet includes a specific instruction as to which neighboring node of the end point of the tunnel the encapsulated packet should be sent, which comprises the “release point”.
It will be noted that in normal forwarding each node decides, irrespective of the node from which it received a packet, the next node to which the packet should be forwarded. In some instances this can give rise to a “loop”. In particular this can occur when the databases (and corresponding forwarding information) are temporarily de-synchronized during a routing transition, that is, where because of a change in the network, a new LSP is propagated. As an example, if node A sends a packet to node Z via node B, comprising the optimum route according to its SPF, a situation can arise where node B, according to its SPF determines that the best route to node Z is via node A and sends the packet back. This can continue for as long as the loop remains although usually the packet will have a maximum hop count after which it will be discarded. Such a loop can be a direct loop between two nodes or an indirect loop around a circuit of nodes.
One solution for avoiding loops during a routing transition is described in co-pending patent application Ser. No. 10/323,358, filed 17 Dec. 2002, entitled “Method and Apparatus for Advertising a Link Cost in a Data Communications Network” of Michael Shand (Shand), the entire contents of which are incorporated by reference for all purposes as if fully set forth herein. According to the solution put forward in Shand, when a node detects deactivation of an adjacent link or node, then instead of advertising the failure of the component, for example by simply removing the link from the LSP, the node that detects deactivation increments the associated link costs and advertises the incremented cost. As a result even when nodes have different LSDBs because of finite propagation and processing time of the LSP carrying the incremented link cost, loops are not set up in the remainder of the network. Once all nodes have updated their LSDBs, the detecting node increments the cost and advertises the incremented cost again. However in some circumstances it is desirable to converge on a common view of a network more quickly than is permitted by this incremental approach.
One alternative approach to dealing with link failure is described in document “Fortifying OSPF/IS-IS Against Link-Failure” by Mikkel Thorup (“Thorup”) which is available at the time of writing on the file “lf_ospf.ps” in the directory “˜mthorup\PAPERS” of the domain “research.att.com” on the World Wide Web. The approach of Thorup is to pre-compute the SPF at each node for each possible link failure. When a link failure is advertised the node forwards along its pre-computed updated path whilst updating the LSDB in the background.
Various problems arise with the approach. Thorup requires increased storage and computing to deal with all possible routes around all possible failures, as well as extra forwarding code requirements. Significantly Thorup does not address the problem of loop formation during a transition.